package main.leetcode.offer.secondround.from03to50;

/** 10-I.斐波那契数列 */
public class ex10I {
    public static void main(String[] args) {
        System.out.println(new ex10I().fib2(44));
        System.out.println(new ex10I().fib(44));
    }

    // 优化写法
    public int fib2(int n) {
        int a = 0, b = 1, sum;
        for (int i = 3; i <= n; ++i) {
            sum = (a + b) % 1000000007;
            a = b;
            b = sum;
        }
        return a;
    }

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        return (fib(n - 1) + fib(n - 2)) % 1000000007;
    }
}
